#include "BinarySearch.h"
#include <cassert>
#include <iterator>
#include <algorithm>
#include <ctime>
#include "common.h"

USING_NS_TEST;
USING_NS_STD;

elloop_test::BinarySearch::BinarySearch() : mLength(20000), valueList(0) {
}

elloop_test::BinarySearch::~BinarySearch() {
	if (valueList) {
		delete [] valueList;
	}
}

BinarySearch* elloop_test::BinarySearch::run() {
	srand(time(0));
	/*	
	_initValueList();
	_doSearch(rand() % mLength);
	*/
	_initValueList();
	_doSearch(rand(), ByValue);
	return this;
}

void elloop_test::BinarySearch::_doSearch( int data , SearchType searchType) {
	sort(valueList, valueList + mLength);
	copy(valueList, valueList+mLength, ostream_iterator<int>(cout, ","));
	cr;
	
	int searchTarget(0); 
	if (searchType == ByValue) {
		searchTarget = data;
	}
	else {
		searchTarget = valueList[data];
	}

	int resultIndex = _bsearchValue(searchTarget);	
	(resultIndex != -1) ? 
		(p("ok, find "), p(valueList[resultIndex]), p(" at "), p(resultIndex)) 
	  : (p("oh, no, no "), p(searchTarget))
	  , cr;
}

int elloop_test::BinarySearch::_bsearchValue( int value ) {
	assert(mLength >= 0);
	if (mLength == 0) {
		return (value == valueList[0]) ? 0 : -1;
	}
	int low = 0;
	int high = mLength - 1;
	int mid = (low + high) / 2;
	while (mid >= low && mid <= high) {
		if (value == valueList[mid]) {
			return mid;
		}
		else if (value < valueList[mid]) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
		mid = (low + high) / 2;
	}
	return -1;
}

void elloop_test::BinarySearch::_initValueList() {
	if (valueList) {
		delete [] valueList;
	}
	valueList = new int[mLength];
	for (int index=0; index < mLength; ++index) {
		valueList[index] = rand();
	}
}
